import java.util.ArrayList;
import java.util.Objects;
import java.util.WeakHashMap;
import java.util.regex.Pattern;

/**
 * Creat with IntelliJ IDEA
 * Description: 链表题练习
 * User:WZW
 * Date:2022-09-04
 * Time:22:37
 */

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    void display() {
        System.out.print(val);
        if (next != null) {
            System.out.print("->");
            next.display();
        }
    }
}

class Solution {

    /*
    解法一
    时间复杂度：O(n)
    空间复杂度：O(1)
     */
    public ListNode ReverseList1(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode cur = head;
        ListNode CurNext = cur.next;
        ListNode pre = cur;
        cur = CurNext;
        while (cur != null) {
            CurNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = CurNext;
        }
        head.next = null;
        head = pre;
        return head;
    }

    /*
    解法二：递归解法
    时间复杂度：O(n)
    空间复杂度：O(n)
     */
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode next = head.next;
        ListNode reverse = ReverseList(next);
        next.next = head;
        head.next = null;
        return reverse;
    }

    /**
     * 链表内指定区间反转
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {

        //找到反转结束节点
        ListNode end = head;
        for (int i = 1; i < n; i++) {
            end = end.next;
        }
        //根据反转起始节点是否为头结点分情况处理
        if (m == 1) {
            reverseBetweenSE(head,end);
            head = end;
        } else {
            ListNode preStart = head;
            for (int i = 1; i < m - 1; i++) {
                preStart = preStart.next;
            }
            reverseBetweenSE(preStart.next,end);
            preStart.next = end;
        }
        return head;
    }

    /*
    给定头尾节点，反转链表
     */
    private void reverseBetweenSE(ListNode start, ListNode end) {
        ListNode cur = start.next;
        start.next = end.next;
        while (cur != end) {
            ListNode CurNext = cur.next;
            cur.next = start;
            start = cur;
            cur = CurNext;
        }
        cur.next = start;
    }

    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(1) ? 调用了函数
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup0 (ListNode head, int k) {
        if (head == null || head.next == null || k == 1) return head;
        int n = 1;
        ListNode start = head;
        ListNode cur = head;
        ListNode curNext = cur.next;
        ListNode preStart = null;// 保存上一组的start
        while (n < k && curNext != null) {
            cur = curNext;
            curNext = curNext.next;
            n++;
            if (n == k) {
                if (start != head) {//不是第一组时
                    //前一组的start.next = 这一组的end（即cur）
                    preStart.next = cur;
                }else {
                    // 是第一组，要把head设为cur，因为反转后cur就是头结点了
                    head = cur;
                }
                // 执行反转
                preStart = start;// 更新preStart的值
                reverse(start, cur);
                start = curNext;
                n = 0;
            }
        }
        return head;
    }


    /*
    解法二：递归
    时间复杂度：O(n)
    空间复杂度：O(n/k)
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if (k <= 1) return head;
        ListNode end = head;
        for (int i = 1; i < k; i++) {
            if (end == null || end.next == null) return head;
            end = end.next;
        }
        // end 为待反转部分的尾部
        // nextHead 为下一个待反转部分的头部
        ListNode nextHead = end.next;
        // 反转
        reverse(head,end);
        // 反转后 head 已经变为尾部，将尾部与下一组反转后的头部连接起来
        head.next = reverseKGroup(nextHead, k);
        return end;
    }

    /*
    反转，返回反转后的头
     */
    private ListNode reverse(ListNode start, ListNode end) {
        ListNode cur = start.next;
        start.next = end.next;
        while (cur != end) {
            ListNode curNext = cur.next;
            cur.next = start;
            start = cur;
            cur = curNext;
        }
        cur.next = start;
        return end;//反转后的头
    }

    /*
    合并两个升序链表
    时间复杂度：O(n)
    空间复杂度：O(1)
     */
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null ) {
            cur.next = list2;
        }
        return head.next;
    }

    /*
    合并K个有序链表
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) return null;
        if (lists.size() == 1) return lists.get(0);
        for (int i = 1; i < lists.size(); i *= 2) {
            for (int j = 0; j < lists.size() - i; j += i*2) {
                ListNode node1 = lists.get(j);
                ListNode node2 = lists.get(j+i);
                lists.set(j,Merge(node1,node2));
            }
        }
        return lists.get(0);
    }

    /*
    判断链表中是否有环
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;//链表为空或只含一个节点
        ListNode fast = head;
        ListNode slow = head;
        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /*
    链表中环的入口节点
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (slow != null && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = pHead;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }

    /**
     * 链表中倒数最后k个结点
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        for (int i = 0; i < k; i++) {
            if (fast != null) {
                fast = fast.next;
            } else {
                return null;
            }
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 删除链表的倒数第n个节点
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pslow = null;
        for (int i = 0; i < n; i++) {
            if (fast != null) {
                fast = fast.next;
            } else {
                return null;
            }
        }
        while (fast != null) {
            fast = fast.next;
            pslow = slow;
            slow = slow.next;
        }
        if (slow == head) return slow.next;
        pslow.next = slow.next;
        return head;
    }

    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode newHead1 = ReverseList(head1);
        ListNode newHead2 = ReverseList(head2);
        return addList(newHead1,newHead2);
    }

    private ListNode addList(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int flg = 0;
        while (cur1 != null && cur2 != null) {
            cur.next = new ListNode(cur1.val + cur2.val + flg);
            if (cur.next.val > 9) {
                // 进位
                flg = 1;
                cur.next.val -= 10;
            } else {
                flg = 0;
            }
            cur = cur.next;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        if (cur1 != null) {
            cur.next = cur1;
            cur1.val += flg;
            if (cur1.val > 9) {
                while (cur1.next != null && cur1.val >9) {
                    cur1.val -= 10;
                    cur1.next.val += 1;
                    cur1 = cur1.next;
                }
                if (cur1.next == null ) {
                    cur1.val -= 10;
                    cur1.next = new ListNode(1);
                }
            }
        }
        if (cur2 != null) {
            cur.next = cur2;
            cur2.val += flg;
            if (cur2.val > 9) {
                while (cur2.next != null && cur2.val >9) {
                    cur2.val -= 10;
                    cur2.next.val += 1;
                    cur2 = cur2.next;
                }
                if (cur2.next == null ) {
                    cur2.val -= 10;
                    cur2.next = new ListNode(1);
                }
            }
        }
        ListNode ret = ReverseList(head.next);
        return ret;
    }

    /**
     * 思路：先分割成单个节点（有序），再合并有序的链表
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 快慢指针找中点
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 分割链表
        ListNode rHead = slow.next;
        slow.next = null;
        // 递归分割
        ListNode left = sortInList(head);
        ListNode right = sortInList(rHead);

        // 归并排序：合并有序链表
        ListNode newHead = new ListNode(-1); //头结点
        ListNode cur = newHead;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left == null ? right : left;
        return newHead.next;
    }

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) return pHead1;
        if (pHead2 == null) return pHead2;
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        int a = 0;
        int b = 0;
        while (cur1 != null) {
            a++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            b++;
            cur2 = cur2.next;
        }
        cur1 = pHead1;
        cur2 = pHead2;
        if (a > b) {
            int n = a - b;
            while (n > 0) {
                n--;
                cur1 = cur1.next;
            }
        } else {
            int n = b - a;
            while (n > 0) {
                n--;
                cur2 = cur2.next;
            }
        }
        while (cur1 != null && cur2 != null && cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }


    /**
     * 判断回文链表
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode right = slow.next;
        slow.next = null;

        //反转右边的链表
        ListNode p = null;
        ListNode cur = right;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = p;
            p = cur;
            cur = curNext;
        }

        while (head != null && p != null) {
            if (head.val != p.val) return false;
            head = head.next;
            p = p.next;
        }
        return true;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 链表的奇偶重排，是按照节点的编号重排！！
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        ListNode o = new ListNode(-1);
        ListNode e = new ListNode(-1);
        ListNode ocur = o;
        ListNode ecur = e;
        ListNode cur = head;
        int n = 1;
        while (cur != null) {
            if (n % 2 == 1) {
                //奇节点
                ocur.next = cur;
                ocur = ocur.next;
            } else {
                ecur.next = cur;
                ecur = ecur.next;
            }
            cur = cur.next;
            n++;
        }
        //连接奇偶链表
        ocur.next = e.next;
        ecur.next = null;
        return o.next;
    }

    /**
     * 删除有序链表中重复的元素 1
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates1 (ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode curNext = cur.next;
            while (curNext != null && cur.val == curNext.val) {
                // 重复节点
                curNext = curNext.next;
            }
            cur.next = curNext;
            cur = cur.next;
        }
        return head;
    }


    /**
     * 删除有序链表中重复的元素 2
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = new ListNode(-1);
        p.next = head;
        ListNode pre = p;
        ListNode cur = p.next;
        boolean flg = false;
        while (cur != null && cur.next != null) {
            ListNode curNext = cur.next;
            while (curNext != null && cur.val == curNext.val) {
                curNext = curNext.next;
                flg = true;
            }
            if (flg) {
                pre.next = curNext;
                flg = false;
                cur = pre.next;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return p.next;
    }
}

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

//        ListNode head = solution.reverseKGroup(null,3);
        ListNode head = solution.deleteDuplicates(node1);
        head.display();

//        System.out.println(solution.isPail(node1));

    }
}
